package 代码记录.剑指offer错题本.hard;

/**
 * @author zx
 * @create 2022-06-23 20:02
 * 组成部分一：确定状态
 *               最后一步：
 *               子问题：
 *               确定dp数组(dp table)以及下标的含义
 *               f(i,j) 代表考虑 s 中以 i 为结尾的子串和 p 中的 j 为结尾的子串是否匹配。
 * 组成部分一：确定状态
 * 最后一步：
 * 子问题：
 * 组成部分二：转移方程
 * 1.p[j]为普通字符：匹配的条件是前面的字符匹配,同时s中的第i个字符和p中的第j位相同.即f(i,j) = f(i - 1,j - 1) && s[i] == p[j]
 * 2.p[j]为 '.'：匹配的条件是前面的字符匹配,s 中的第 i 个字符可以是任意字符.即 f(i,j) = f(i - 1, j - 1) && p[j] == '.'
 * 3.p[j]为 '*'：可匹配任意长度的字符,可以匹配 0 个字符、匹配 1 个字符、匹配 2 个字符
 * 3.1. 当匹配为 0 个：f(i,j) = f(i, j - 1)
 * 3.2. 当匹配为 1 个：f(i,j) = f(i - 1, j - 1)
 * 3.3. 当匹配为 2 个：f(i,j) = f(i - 2, j - 1)
 * ...
 * 3.k. 当匹配为 k 个：f(i,j) = f(i - k, j - 1)
 * 因此对于 p[j] = '*' 的情况,想要 f(i, j) = true,只需要其中一种情况为 true 即可.也就是状态之间是[或]的关系：
 * f[i][j] = f[i][j - 1] || f[i - 1][j - 1] || ... || f[i - k][j - 1] (i >= k)
 * f[i][j] = f[i][j − 1] || f[i − 1][j − 1] || ... || f[i − k][j − 1] (i >= k)
 * 这意味着我们要对 k 种情况进行枚举检查吗？
 * 其实并不用,对于这类问题,我们通常可以通过[代数]进简化,将i - 1代入上述的式子：
 * f[i - 1][j] = f[i - 1][j - 1] || f[i - 2][j - 1] || ... || f[i - k][j - 1] (i >= k)
 * f[i − 1][j]=f[i − 1][j − 1] || f[i − 2][j − 1] || ... || f[i − k][j − 1](i >= k)
 * 可以发现,f[i - 1][j] 与 f[i][j] 中的 f[i][j - 1] 开始的后半部分是一样的,因此有：
 * f[i][j] = f[i][j - 1] || f[i - 1][j] (i >= 1)
 * f[i][j]=f[i][j − 1] || f[i − 1][j](i >= 1)
 * 组成部分三：初始条件和边界情况
 * 组成部分四：计算顺序
 *
 * 编码细节：
 * 通过上述的推导过程,发现设计不少的[回退检查]操作(即遍历到 i 位,要回头检查 i - 1 等),因此可以将[哨兵技巧]应用到本题
 * 往两个字符串的头部插入哨兵,对于 p[j] = '.' 和 p[j] = 普通字符 的情况
 * 想要为 true,其实有共同的条件 f[i - 1][j - 1] == true,因此可以合到一起来做
 */
public class 通配符匹配_44 {
    /**
     * @return 宫水三叶题解
     */
    public boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length();
        //技巧：往原字符头部插入空格,这样得到char数组是从1开始,可以使得f[0][0] = true,
        //可以将true这个结果滚动下去
        s = " " + s;
        p = " " + p;
        char[] c1 = s.toCharArray();
        char[] c2 = p.toCharArray();
        //f(i,j)代表考虑s中的1 ~ i字符和p中的1 ~ j字符是否匹配
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (c2[j] == '*') {
                    dp[i][j] = dp[i][j - 1] || (i - 1 >= 0 && dp[i - 1][j]);
                } else {//情况1和情况2
                    dp[i][j] = i - 1 >= 0 && dp[i - 1][j - 1] && (c1[i] == c2[j] || c2[j] == '?');
                }
            }
        }
        return dp[n][m];
    }
}
